package com.yangzhe.algorithm.c034;

// 每k个节点一组翻转链表
// 测试链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/
public class Code02_ReverseNodesInkGroup_LeetCode {

    // 不要提交这个类
    public static class ListNode {
        public int val;
        public ListNode next;
    }

    // 提交如下的方法
    public static ListNode reverseKGroup(ListNode head, int k) {
        if (k == 1) {
            return head;
        }

        // 1. 第一组k个节点需要特殊处理，翻转之后的头节点就是答案的头节点
        HeadAndEnd headAndEnd = getHeadAndEnd(head, k);
        HeadAndEnd resverHeadAndEnd = reverse(headAndEnd.head, headAndEnd.end);

        ListNode resultHead = resverHeadAndEnd.head;

        // 记录前一组k个节点
        HeadAndEnd preHeadAndEnd = resverHeadAndEnd;
        // 当前准备处理的k个节点
        HeadAndEnd currentHeadAndEnd = getHeadAndEnd(resverHeadAndEnd.end.next, k);
        while (currentHeadAndEnd != null) {
            // 翻转
            HeadAndEnd reverse = reverse(currentHeadAndEnd.head, currentHeadAndEnd.end);
            // 将上一组和翻转之后的链表连接依赖
            preHeadAndEnd.end.next = reverse.head;

            preHeadAndEnd = reverse;
            currentHeadAndEnd = getHeadAndEnd(reverse.end.next, k);
        }

        return resultHead;
    }

    /**
     * 从当前节点数k个节点，并返回开始节点和结束节点。如果不足k个则返回null
     *
     * @param head 当前节点
     * @param k    k个
     * @return HeadAndEnd.head表示头，HeadAndEnd.end表示尾
     */
    private static HeadAndEnd getHeadAndEnd(ListNode head, int k) {
        HeadAndEnd headAndEnd = new HeadAndEnd();
        headAndEnd.head = head;

        while (k != 0) {
            // 不足k个返回null
            if (head == null) {
                return null;
            }
            headAndEnd.end = head;
            head = head.next;
            k--;
        }

        return headAndEnd;
    }

    /**
     * 翻转head到end之间的链表
     *
     * @param head 头节点
     * @param end  尾节点
     * @return 翻转后的链表，HeadAndEnd.head表示头，HeadAndEnd.end表示尾
     */
    public static HeadAndEnd reverse(ListNode head, ListNode end) {
        // 记录原来的结束节点指针，并断联
        ListNode preEndNext = end.next;
        end.next = null;

        // 开始和结束指针翻转
        HeadAndEnd headAndEnd = new HeadAndEnd();
        headAndEnd.head = end;
        headAndEnd.end = head;

        // 链表内部翻转
        ListNode pre = null;
        ListNode next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }

        // 翻转之后和之前结束的指针连接上
        headAndEnd.end.next = preEndNext;
        return headAndEnd;
    }

    protected static class HeadAndEnd {
        ListNode head;
        ListNode end;
    }
}
